//////////////////////////////////////////////////////////////////////////
//
// This file is a part of XORT project.
//
// PROJECT:         Xort compiler
// FILE:            optimizer.cpp
// AUTHOR:          Vladimir Gumenuk
// DATE:            26-Sep-2014
// MODIFICATIONS:
//
//
//     Copyright(c) 2014, Vladimir Gumenuk
//     All rights reserved.
//
//     Redistribution and use in source and binary forms, with or without modification, 
//     are permitted provided that the following conditions are met :
//
//     1. Redistributions of source code must retain the above copyright notice, 
//        this list of conditions and the following disclaimer.
//     2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and 
//        the following disclaimer in the documentation and / or other materials provided with the distribution.
//     3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse 
//        or promote products derived from this software without specific prior written permission.
//
//     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 
//     ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 
//     OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 
//     THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
//     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
//     OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
//     HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 
//     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 
//     EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
//////////////////////////////////////////////////////////////////////////

/*
            This stuff does several peep-hole optimizations:
    case 1
000001 - [ip:000000]:   @stkvar_1; [9302]     int dwStorage = 0;
000002 - [ip:000001]:       load.c.s4    0        <- can be removed!
000003 - [ip:000002] :      load.c.s4    0        
000004 - [ip:000003] :      store.s.s4   S[1]     <- can be removed!

    case 1.1
000046-[ip:000045]:    @stkvar_3
000047-[ip:000046]:        load.c.p    0x00000000 <- can be removed!
000048-[ip:000047]:        load.s.p    S[1]
000049-[ip:000048]:        store.s.p    S[3]      <- can be removed! 

    case 1.2
000028-[ip:000027]:    @stkvar_2                           ;[9619]         Token Tok = lex_GetLastToken();
000029-[ip:000028]:        load.c.p    0x00000000 <- can be removed!         
000030-[ip:000029]:        calli.p    64                   
000031-[ip:000030]:        store.s.p    S[2]      <- can be removed!         

    case 2
000005-[ip:000004]:        enter                  <- can be removed!
000006-[ip:000005]:        load.c.u4    0
000007-[ip:000006]:        ret.u4

    case 3
000017-[ip:000016]:    @stkvar_2                           ;[1147]         dword dwRead = fread( buf, 1, 4, m_hFile );
000018-[ip:000017]:        load.c.u4    0         <- can be removed!
000019-[ip:000018]:        load.s.p    S[1]
000020-[ip:000019]:        load.c.u4    1
000021-[ip:000020]:        load.c.u4    4
000022-[ip:000021]:        load.ti.u4    T[2]
000023-[ip:000022]:        calli.u4    18
000024-[ip:000023]:        store.s.u4    S[2]    <- can be removed!

    case 3.1
000004-[ip:000003]:    @stkvar_1                           ;[9202]     Symbol pSym = symList.next();
000005-[ip:000004]:        load.c.p    0x00000000 <- can be removed!   
000006-[ip:000005]:        load.s.p    S[-3]
000007-[ip:000006]:        load.c.u2    8
000008-[ip:000007]:        invoke.p
000009-[ip:000008]:        store.s.p    S[1]      <- can be removed!

    case 4
000016-[ip:000015]:        store.s.s2    S[1]              
000017-[ip:000016]:        load.s.s2    S[1]                   ;[11060]     return x;
000018-[ip:000017]:        ret.s2                          
                     can be changed like the following:
                           dup
                           store.s.s2    S[1]
                           ret.s2
                      or even just like this, seems that assigning to stack variable before exit is just a wasting time...
                           ret.s2

    case 5
00000018-[ip:00000017]:        drop               <- can be removed, as it has no sence before p_leave...
00000019-[ip:00000018]:        leave                               ;[000003B6]         }

    case 5.1
000000A8-[ip:000000A7]:        drop               <- can be removed, as it has no sence before ret.v
000000A9-[ip:000000A8]:        ret.v                               ;[00002F3B] }

    case 6 TODO - this is quite dificult case... not done yet
00000018-[ip:00000017]:    @stkvar_2
00000019-[ip:00000018]:        load.s.p    S[65535]
0000001A-[ip:00000019]:        load.c.u4    1
0000001B-[ip:0000001A]:        load.s.u4    S[1]
0000001C-[ip:0000001B]:        load.ti.u4    T[2]
0000001D-[ip:0000001C]:        calli.u4    17
0000001E-[ip:0000001D]:        load.s.u4    S[2]     <- can be removed!
0000001F-[ip:0000001E]:        ret.u4

    case 7
0000000D-[ip:0000000C]:        leave                 <- can be removed!
0000000E-[ip:0000000D]:    __@L97:
0000000F-[ip:0000000E]:    __@L98:
00000010-[ip:0000000F]:        ret.v

    case 8:
000004D4-[ip:000004D3]:        enter                 <- can be removed!
000004D5-[ip:000004D4]:        load.c.u1    0x0D
000004D6-[ip:000004D5]:        store.s.u1    S[5]
000004D7-[ip:000004D6]:        leave                 <- can be removed!

    case 9:
00000027-[ip:00000026]:        goto.c.s2    __@L3597
00000028-[ip:00000027]:        goto.c.s2    __@L3598   <- can be removed! This is the result of deep while - if - break generation...

    case 10
00000168-[ip:00000167]:        enter                 <- can be removed!
00000169-[ip:00000168]:        calli.v       146
0000016A-[ip:00000169]:        leave                 <- can be removed!

    case 11 - optimize ++i in for
000014-[ip:000013]:        load.s.s4    S[1]                   ;[8]     for( i = 0; i < 10; ++i )
000015-[ip:000014]:        inc.s4
000016-[ip:000015]:        dup
000017-[ip:000016]:        store.s.s4    S[1]
000018-[ip:000017]:        leave                               ;[11]     }
000019-[ip:000018]:        goto.c.s2    __@L1
    this sequence can be replaced by the following:
                           inc.s.s4     S[1]
                           leave
                           goto.c.s2    __@L1
----------------------------------------------------------------------------
TODO:
this should be done in second path:

The general rule for this: if after execution any instructions betweem enter-leave the stack is unchanged - enter/leave can be removed.
Small addition: instructions should not refer to any stack variables, since enter adds stack frame. In this case nothing can be removed.
0000023B-[ip:0000023A]:        enter                 <- can be removed!
0000023C-[ip:0000023B]:        load.c.u4    51
0000023D-[ip:0000023C]:        load.m.p    M[2279]
0000023E-[ip:0000023D]:        load.c.u2    2
0000023F-[ip:0000023E]:        put.u4
00000240-[ip:0000023F]:        leave                 <- can be removed!

*/
#include "xort.h"

STATIC int optimize_function( SymbolRef Func )
{
    int iRet = XORT_OK;

    dword dwNumInstr = Func.m_Code.count();
    if( dwNumInstr == 0 )
        return iRet;

    INSTRUCTION_ARRAY   arCode;     // new code array
    dword dwIdx = 0;

    while( dwIdx < dwNumInstr )
    {
        int bMatched = FALSE;

        InstructionData PTR instrData = Func.getInstructionByIndex( dwIdx );
        // case 1
        if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_stkvar ) // p_stkvar marker, case 1
        {
            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_load ) // p_load
            {
                byte bType = MEMBER_PTR( instrData2 )m_bTypeAddr & 0xF0;
                byte bAddr = MEMBER_PTR( instrData2 )m_bTypeAddr & 0x0F;

                if( bAddr == a_c )
                {
                    InstructionData PTR instrData3 = Func.getInstructionByIndex( dwIdx + 2 );
                    if( instrData3 && ( MEMBER_PTR( instrData3 )m_bInstrCode == p_load || MEMBER_PTR( instrData3 )m_bInstrCode == p_call ) ) // p_load || p_call
                    {
                        byte bType2 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0xF0;
                        byte bAddr2 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0x0F;

                        if( ( bAddr2 == a_c || bAddr2 == a_m || bAddr2 == a_s || bAddr2 == a_ti ) && bType == bType2 ) // 1, 1.1, 1.2
                        {
                            InstructionData PTR instrData4 = Func.getInstructionByIndex( dwIdx + 3 );
                            if( instrData4 && MEMBER_PTR( instrData4 )m_bInstrCode == p_store ) // p_store
                            {
                                byte bType3 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0xF0;
                                byte bAddr3 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0x0F;

                                if( bAddr3 == a_s && bType == bType3 && MEMBER_PTR( instrData )m_Value._s2 == MEMBER_PTR( instrData4 )m_Value._s2 )
                                {
                                    bMatched = TRUE; // case 1 matched!
                                    arCode.add( instrData ); // leave p_stkvar
                                    arCode.add( instrData3 ); // leave actual data
                                    dwIdx += 3; // continue from next instruction
                                }
                            }
                        }
                    }
                    
                    if( !bMatched ) // fall to case 3 and 3.1 - process all instructions between p_stkvar and p_store
                    {
                        INSTRUCTION_ARRAY arCodeTemp;
                        dword dwStartIdx = dwIdx + 2; // start where we left

                        arCodeTemp.add( instrData ); // leave p_stkvar

                        InstructionData PTR instrTmp = Func.getInstructionByIndex( dwStartIdx );
                        while( instrTmp && MEMBER_PTR( instrTmp )m_bInstrCode != p_store && MEMBER_PTR( instrTmp )m_bInstrCode != p_enter && MEMBER_PTR( instrTmp )m_bInstrCode != p_stkvar  ) {
                            arCodeTemp.add( instrTmp );
                            ++dwStartIdx;
                            instrTmp = Func.getInstructionByIndex( dwStartIdx );
                        }

                        if( instrTmp && MEMBER_PTR( instrTmp )m_bInstrCode == p_store )
                        {
                            byte bTypeTemp = MEMBER_PTR( instrTmp )m_bTypeAddr & 0xF0;
                            byte bAddrTemp = MEMBER_PTR( instrTmp )m_bTypeAddr & 0x0F;

                            // if address byte is stack AND types of first p_load are matched AND index of p_stkvar equals to index of p_store...
                            if( bAddrTemp == a_s && bType == bTypeTemp && MEMBER_PTR( instrData )m_Value._s2 == MEMBER_PTR( instrTmp )m_Value._s2 )
                            {
                                bMatched = TRUE; // case 3 matched!
                                dword i = 0;
                                dword dwNumInstr = arCodeTemp.count();
                                while( i < dwNumInstr ) {
                                    arCode.add( arCodeTemp.get( i ) );
                                    ++i;
                                }
                                
                                dwIdx = dwStartIdx; // continue from next instruction
                            }
                        }
                    }
                }
            }
        }
        else if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_enter ) // case 2 - remove p_enter instruction
        {
            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_load ) // p_load
            {
                byte bType2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0xF0;
                byte bAddr2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0x0F;

                InstructionData PTR instrData3 = Func.getInstructionByIndex( dwIdx + 2 );
                if( instrData3 && MEMBER_PTR( instrData3 )m_bInstrCode == p_ret ) // p_ret
                {
                    byte bType3 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0xF0;
                    byte bAddr3 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0x0F;

                    if( bType2 == bType3 )
                    {
                        bMatched = TRUE; // case 2 matched!
                        arCode.add( instrData2 ); // leave p_load
                        arCode.add( instrData3 ); // leave p_ret
                        dwIdx += 2;
                    }
                }
                else if( instrData3 && MEMBER_PTR( instrData3 )m_bInstrCode == p_store ) // p_store case 8
                {
                    byte bType3 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0xF0;
                    byte bAddr3 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0x0F;

                    InstructionData PTR instrData4 = Func.getInstructionByIndex( dwIdx + 3 );
                    if( instrData4 && MEMBER_PTR( instrData4 )m_bInstrCode == p_leave )
                    {
                        byte bType4 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0xF0;
                        byte bAddr4 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0x0F;

                        if( bType2 == bType3 )
                        {
                            bMatched = TRUE;    // case 8 matched!
                            arCode.add( instrData2 ); // leave p_load
                            arCode.add( instrData3 ); // leave p_store
                            dwIdx += 3;
                        }
                    }
                }
            }
            else if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_calli ) // case 10
            {
                byte bType2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0xF0;
                
                InstructionData PTR instrData3 = Func.getInstructionByIndex( dwIdx + 2 );
                if( instrData3 && MEMBER_PTR( instrData3 )m_bInstrCode == p_leave ) // p_leave
                {
                    if( bType2 == t_v )
                    {
                        bMatched = TRUE; // case 10 mached
                        arCode.add( instrData2 ); // leave only calli instruction.
                        dwIdx += 2;
                    }
                }
            }
        }
        else if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_store ) // case 4 - remove 2 instructions
        {
            byte bType = MEMBER_PTR( instrData )m_bTypeAddr & 0xF0;
            byte bAddr = MEMBER_PTR( instrData )m_bTypeAddr & 0x0F;

            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_load ) // p_load
            {
                byte bType2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0xF0;
                byte bAddr2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0x0F;

                if( bAddr == bAddr2 && bType == bType2 && MEMBER_PTR( instrData )m_Value._s2 == MEMBER_PTR( instrData2 )m_Value._s2 )
                {
                    InstructionData PTR instrData3 = Func.getInstructionByIndex( dwIdx + 2 );
                    if( instrData3 && MEMBER_PTR( instrData3 )m_bInstrCode == p_ret ) // p_ret
                    {
                        byte bType3 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0xF0;
                        byte bAddr3 = MEMBER_PTR( instrData3 )m_bTypeAddr & 0x0F;

                        if( bType3 == bType2 )
                        {
                            bMatched = TRUE; // case 4 matched!
                            arCode.add( instrData3 ); // leave p_ret only
                            dwIdx += 2;
                        }
                    }
                }
            }
        }
        else if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_drop ) // case 5
        {
            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_leave ) // p_leave
            {
                bMatched = TRUE; // case 5 matched!
                arCode.add( instrData2 ); // leave p_leave only
                dwIdx += 1;
            }
            else if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_ret ) // case 5.1
            {
                byte bType2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0xF0;
                if( bType2 == t_v )
                {
                    bMatched = TRUE; // case 5.1 matched!
                    arCode.add( instrData2 ); // leave ret.v only
                    dwIdx += 1;
                }
            }
        }
        else if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_leave ) // case 7
        {
            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_label ) // p_label
            {
                InstructionData PTR instrData3 = Func.getInstructionByIndex( dwIdx + 2 );
                if( instrData3 && MEMBER_PTR( instrData3 )m_bInstrCode == p_label ) // p_label
                {
                    InstructionData PTR instrData4 = Func.getInstructionByIndex( dwIdx + 3 );
                    if( instrData4 && MEMBER_PTR( instrData4 )m_bInstrCode == p_ret ) // p_label
                    {
                        byte bType4 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0xF0;
                        if( bType4 == t_v )
                        {
                            bMatched = TRUE;  // case 7 matched
                            arCode.add( instrData2 ); // remove first p_leave instruction
                            arCode.add( instrData3 );
                            arCode.add( instrData4 );
                            dwIdx += 3;
                        }
                    }
                }
            }
        }
        else if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_goto ) // case 9
        {
            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && MEMBER_PTR( instrData2 )m_bInstrCode == p_goto ) // p_leave
            {
                bMatched = TRUE; // case 9 matched!
                arCode.add( instrData ); // leave first p_goto only, second is unrechable
                dwIdx += 1;
            }
        }
        else if( instrData && MEMBER_PTR( instrData )m_bInstrCode == p_load ) // p_load,  case 11
        {
            byte bType = MEMBER_PTR( instrData )m_bTypeAddr & 0xF0;
            byte bAddr = MEMBER_PTR( instrData )m_bTypeAddr & 0x0F;

            InstructionData PTR instrData2 = Func.getInstructionByIndex( dwIdx + 1 );
            if( instrData2 && (MEMBER_PTR( instrData2 )m_bInstrCode == p_inc || MEMBER_PTR( instrData2 )m_bInstrCode == p_dec ) )// p_inc / p_dec
            {
                byte bType2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0xF0;
                byte bAddr2 = MEMBER_PTR( instrData2 )m_bTypeAddr & 0x0F;

                InstructionData PTR instrData3 = Func.getInstructionByIndex( dwIdx + 2 );
                if( instrData3 && MEMBER_PTR( instrData3 )m_bInstrCode == p_dup ) // p_dup
                {
                    InstructionData PTR instrData4 = Func.getInstructionByIndex( dwIdx + 3 );
                    if( instrData4 && MEMBER_PTR( instrData4 )m_bInstrCode == p_store ) // p_store
                    {
                        byte bType4 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0xF0;
                        byte bAddr4 = MEMBER_PTR( instrData4 )m_bTypeAddr & 0x0F;

                        InstructionData PTR instrData5 = Func.getInstructionByIndex( dwIdx + 4 );
                        if( instrData5 && MEMBER_PTR( instrData5 )m_bInstrCode == p_leave ) // p_leave
                        {
                            InstructionData PTR instrData6 = Func.getInstructionByIndex( dwIdx + 5 );
                            if( instrData6 && MEMBER_PTR( instrData6 )m_bInstrCode == p_goto ) // p_goto
                            {
                                if( bType == bType2 && bType2 == bType4 && bAddr == bAddr4 && bAddr2 == a_0 && MEMBER_PTR( instrData )m_Value._s2 == MEMBER_PTR( instrData4 )m_Value._s2 )
                                {
                                    // let's just change the first instruction and use it:
                                    MEMBER_PTR( instrData )m_bInstrCode = MEMBER_PTR( instrData2 )m_bInstrCode;
                                    MEMBER_PTR( instrData )m_strInstr.Empty();

                                    int iRet = decode_instr_text( DEREF( instrData ) );
                                    if( iRet == XORT_OK )
                                    {
                                        bMatched = TRUE; // case 11

                                        arCode.add( instrData ); // inc.s.s4   S[1]
                                        arCode.add( instrData5 ); // leave
                                        arCode.add( instrData6 ); // goto...
                                        dwIdx += 5;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
                
        if( !bMatched )
        {
            arCode.add( instrData );
        }

        ++dwIdx;
    }

    arCode.copy( Func.m_Code );
    
    return iRet;
}

int optimize_program( SYMBOLLIST symList )
{
    int iRet = XORT_OK;

    symList.reset_to_end();

    CONST symbolref PTR Sym = symList.prev();
    while( Sym )
    {
        if( MEMBER_PTR( DEREF( Sym ) )m_SymKind == sk_proc )
        {
            iRet = optimize_function( DEREF( DEREF( Sym ) ) );
        }
        else if( MEMBER_PTR( DEREF( Sym ) )m_SymKind == sk_obj )
        {
            iRet = optimize_program( MEMBER_PTR( DEREF( Sym ) )m_listMembers );
        }

        if( iRet != XORT_OK )
            break;

        Sym = symList.prev();
    }


    return iRet;
}
